#include <iostream>
#include <vector>
#include <algorithm>
#define int size_t  //这样全局变量不会出问题了
using namespace std;

// DFS 函数，寻找从 start 到 end 的所有路径(DFS算法确认无误)
void dfs(int start, int end, const vector<vector<int>>& roadlength, vector<bool>& visited, vector<int>& current_path, vector<vector<int>>& all_paths) {
    visited[start] = true; // 标记当前节点为已访问
    current_path.push_back(start); // 将当前节点加入路径

    if (start == end) {
        all_paths.push_back(current_path); // 找到一条路径，保存到 all_paths 中
    } else {
        // 遍历所有邻接节点
        for (int i = 0; i < roadlength.size(); i++) {
            if (roadlength[start][i] != INT_MAX && !visited[i]) { // 如果道路存在且未访问
                vector<int> new_path = current_path;
                dfs(i, end, roadlength, visited, new_path, all_paths); // 递归搜索
            }
        }
    }

    // 回溯
    if (!current_path.empty()) {
        current_path.pop_back();
    }
    visited[start] = false;
}

// 检测当前车辆路径组合是否会导致堵车
bool checkTraffic(const vector<vector<int>>& combination, const vector<vector<int>>& roadlength, const vector<vector<int>>& restrictions) {
    //验证是否遍历了每一种组合
    /*static int numbers=0;
    cout<<++numbers<<endl;
    int carid=0;
    for (vector<int> road: combination) {
        printf("carid:%d, ",++carid);
        for (int i:road){
            printf("%d ",i+1);
        }
        printf("\n");
    }*/
    
    int max_time = 0; // 记录所有车辆行驶的最大时间
    vector<vector<int>> vehicle_timelines; // 每辆车的行驶时间线

    // 计算每辆车的行驶时间线
    for (const vector<int>& path : combination) {
        vector<int> timeline;
        int current_time = 0;
        for (int i = 1; i < path.size(); i++) {
            int u = path[i - 1];
            int v = path[i];
            int length = roadlength[u][v];
            for (int t = current_time; t < current_time + length; t++) {
                timeline.push_back(u); // 车辆在路段 u->v 上行驶
            }
            current_time += length;
        }
        vehicle_timelines.push_back(timeline);
        max_time = max(max_time, current_time);
    }

    // 动态跟踪每条道路的车流量
    for (int t = 0; t < max_time; t++) {
        vector<vector<int>> flow(roadlength.size(), vector<int>(roadlength.size(), 0)); // 当前时间点的车流量

        // 更新每条道路的车流量
        for (int i = 0; i < vehicle_timelines.size(); i++) {
            if (t < vehicle_timelines[i].size()) {
                int u = vehicle_timelines[i][t];
                int v = (t + 1 < vehicle_timelines[i].size()) ? vehicle_timelines[i][t + 1] : -1;
                if (v != -1) {
                    flow[u][v]++;
                }
            }
        }

        // 检查是否堵车
        for (int u = 0; u < roadlength.size(); u++) {
            for (int v = 0; v < roadlength.size(); v++) {
                if (flow[u][v] > restrictions[u][v]) {
                    return false; // 堵车
                }
            }
        }
    }
    cout<<"True"<<endl;
    return true; // 没有堵车
}

// 计算当前组合的总路径长度
int calculateTotalLength(const vector<vector<int>>& combination, const vector<vector<int>>& roadlength) {
    int total_length = 0;
    for (const vector<int>& path : combination) {
        for (int i = 1; i < path.size(); i++) {
            int u = path[i - 1];
            int v = path[i];
            total_length += roadlength[u][v];
        }
    }
    return total_length;
}

// 遍历所有车辆路径组合的函数
void traverseCombinations(const vector<vector<vector<int>>>& all_cars_paths, int car_index, vector<vector<int>>& current_combination, vector<vector<vector<int>>>& all_combinations) {
    // 如果已经处理完所有车辆，保存当前组合
    if (car_index == all_cars_paths.size()) {
        all_combinations.push_back(current_combination);
        return;
    }

    // 遍历当前车辆的所有路径方案
    for (const vector<int>& path : all_cars_paths[car_index]) {
        current_combination.push_back(path); // 选择当前路径方案
        traverseCombinations(all_cars_paths, car_index + 1, current_combination, all_combinations); // 递归处理下一辆车
        current_combination.pop_back(); // 回溯，撤销选择
    }
}

// 找到不堵车且总路径长度最短的组合
void findBestCombination(const vector<vector<vector<int>>>& all_cars_paths, const vector<vector<int>>& roadlength, const vector<vector<int>>& restrictions) {
    vector<vector<int>> best_combination; // 存储最短组合
    int min_total_length = INT_MAX; // 记录最短组合的总路径长度

    // 遍历所有车辆路径组合
    vector<vector<int>> current_combination;
    vector<vector<vector<int>>> all_combinations;
    traverseCombinations(all_cars_paths, 0, current_combination, all_combinations);

    for (const vector<vector<int>>& combination : all_combinations) {
        // 检查是否堵车
        if (checkTraffic(combination, roadlength, restrictions)) {
            // 计算总路径长度
            int total_length = calculateTotalLength(combination, roadlength);

            // 如果总路径长度更短，更新最短组合
            if (total_length < min_total_length) {
                min_total_length = total_length;
                best_combination = combination;
            }
        }
    }

    // 输出最短组合
    if (!best_combination.empty()) {
        cout << "Best combination (total length: " << min_total_length << "):" << endl;
        for (int i = 0; i < best_combination.size(); i++) {
            cout << "Car " << i + 1 << " path: ";
            for (int node : best_combination[i]) {
                cout << node + 1 << " ";
            }
            cout << endl;
        }
    } else {
        cout << "No valid combination found!" << endl;
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    // 动态分配二维数组
    vector<vector<int>> roadlength(N, vector<int>(N, INT_MAX)); // 存储道路长度
    vector<vector<int>> restrictions(N, vector<int>(N)); // 存储道路的流量限制
    vector<vector<int>> cars(M, vector<int>(2)); // 存储每辆车的起点和终点

    // 读取道路长度
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> roadlength[i][j];
            if (roadlength[i][j] == 0 && i != j) {
                roadlength[i][j] = INT_MAX; // 如果道路长度为 0，则距离为无穷大
            }
        }
    }

    // 读取道路的流量限制
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> restrictions[i][j];
        }
    }

    // 读取每辆车的起点和终点
    for (int i = 0; i < M; i++) {
        cin >> cars[i][0] >> cars[i][1];
        cars[i][0]--; // 将输入的起点和终点转换为从 0 开始的索引
        cars[i][1]--;
    }

    // 存储每辆车的所有路径
    vector<vector<vector<int>>> all_cars_paths(M); // 每辆车的所有路径

    // 为每辆车找到所有路径
    for (int i = 0; i < M; i++) {
        int start = cars[i][0];
        int end = cars[i][1];
        vector<bool> visited(N, false); // 记录节点是否被访问
        vector<int> current_path; // 记录当前路径
        vector<vector<int>> all_paths; // 存储所有路径

        dfs(start, end, roadlength, visited, current_path, all_paths);

        all_cars_paths[i] = all_paths; // 保存当前车辆的所有路径
    }
    for (int i=0;i<M;i++){
        cout << "Car " << i+1 << " paths: " << all_cars_paths[i].size() << endl;
        for(auto path: all_cars_paths[i]){
            for(int node: path){
                cout << node+1 << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
    // 找到不堵车且总路径长度最短的组合
    findBestCombination(all_cars_paths, roadlength, restrictions);

    return 0;
}